
from libc.stdint cimport uint64_t as u64, uint32_t as u32, uint8_t as u8, uint16_t as u16, int32_t as i32,\
    int16_t as i16, int8_t as i8, int64_t as i64, UINT64_MAX, UINT32_MAX, UINT16_MAX, INT64_MAX, INT64_MIN, UINT32_MAX, UINT8_MAX
cdef u64 UINT40_MAX=1<<40-1, UINT48_MAX=1<<48-1, UINT24_MAX=1<<24-1

ctypedef unsigned int uint

from libc.string cimport memcpy, memcmp, memset, strlen, memmove
from libc.stdlib cimport malloc, free, realloc
from cpython.time cimport time as get_time_double
from cpython.mem cimport PyMem_Free,PyMem_Malloc,PyMem_Calloc,PyMem_Realloc, PyMem_RawMalloc, PyMem_RawFree

from cpython.list cimport PyList_New, PyList_SetItem, PyList_GetSlice, PyList_GetItem, PyList_GET_ITEM,  PyList_SET_ITEM, PyList_AsTuple, PyList_Insert
from cpython.ref cimport Py_INCREF, PyTypeObject, Py_TYPE
from cpython.buffer cimport PyBuffer_FromContiguous
from cpython.unicode cimport (PyUnicode_Compare, PyUnicode_FromStringAndSize, PyUnicode_FromKindAndData, PyUnicode_1BYTE_KIND,
        PyUnicode_2BYTE_KIND, PyUnicode_4BYTE_KIND,PyUnicode_4BYTE_DATA, PyUnicode_2BYTE_DATA, PyUnicode_1BYTE_DATA,
    Py_UCS1, Py_UCS2, PyUnicode_KIND, PyUnicode_DATA)
from cpython.bytes cimport PyBytes_FromString, PyBytes_FromStringAndSize, PyBytes_AsString
from cpython.float cimport PyFloat_FromDouble
from cpython.tuple cimport PyTuple_New, PyTuple_SetItem, _PyTuple_Resize, PyTuple_GET_ITEM, PyTuple_SET_ITEM
from cpython.ref cimport Py_INCREF, Py_DECREF
from cpython.array cimport array, resize, resize_smart, extend_buffer, copy, newarrayobject, clone
from cpython.object cimport Py_SIZE, PyObject

from libc.stdio cimport FILE, fopen, fclose, fdopen, fread, fwrite, fseek, ftell, fseek, rewind, fflush, SEEK_SET, SEEK_CUR, SEEK_END, feof, ferror, setvbuf

import threading, time, os
import collections
cdef inline div(u64 a, u64 b):
    return <u64>(a/b)

cdef extern from *:
    '''
    #if defined(_WIN64) || defined(_WIN32) || defined(__WIN32__) || defined(__NT__) || defined(WIN32)
        #include <windows.h>
        #include <processthreadsapi.h>
        #include<process.h>
        #include<io.h>
        inline void fsync_stream(FILE* stream){
            int fd = _fileno(stream);
            _commit(fd);
        }
        inline void fsync_fd(int fd){
            _commit(fd);
        }
        inline void my_thread_yield(){
            SwitchToThread();
        }
        inline void my_thread_sleep(){
            Sleep(0);
        }

    #elif defined(_POSIX_VERSION)
        #include<pthread.h>
        #include<unistd.h>
        inline void fsync_stream(FILE* stream){
            int fd = _fileno(stream);
            _commit(fd);
        }
        inline void fsync_fd(int fd){
            fsync(fd);
        }
        inline void my_thread_yield(){
            pthread_yield();
        }
        inline void my_thread_sleep(){
            sleep(0);
        }

    #endif
    '''
    void thread_sleep(int t) nogil
    void thread_yield() nogil
    void my_thread_sleep() nogil
    void my_thread_yield() nogil


cdef:
    set empty_set=set()
    list empty_list=[]

cdef bytes char37=b'0123456789_abcdefghijklmnopqrstuvwxyz'
assert len(char37)==37
cdef u8* char37s = <u8*><char*>char37
test_char37_to_num()
cpdef test_char37_to_num():
    cdef uint i
    cdef u8 c, cc
    for i in range(37):
        c=char37s[i]
        cc=char37_to_num(c)
        #print(i, c, cc)
        assert i==cc

cpdef u64 char37_to_num(u8 char):
    if char< 0x5F: #0-9
        return char-0x30
    elif char>0X5F: #a-z
        return char-86 #char-0x61+11
    else: #_
        return 10

cpdef unicode num_to_char37s(u64 num):
    cdef u64 l=37, i, idx_chars=0, n=num
    cdef u8[13] chars # 37^13 > 2^64
    #
    while(n):
        i=n%37
        chars[idx_chars]=char37s[i]
        idx_chars+=1
        n = <u64>(n/37)
    return PyUnicode_FromKindAndData(PyUnicode_1BYTE_KIND, chars, idx_chars)

ctypedef fused pyucs:
    Py_UCS1
    Py_UCS2
    Py_UCS4

cdef u64 pyucs_to_num(pyucs* s, uint len):
    cdef u64 num=0, i, cur=1, ix
    for i in range(len):
        ix = char37_to_num(s[i])
        num += ix*cur
        cur *= 37
    return num

cpdef u64 char37s_to_num(unicode s):
    cdef uint kind = PyUnicode_KIND(s)
    if kind == PyUnicode_1BYTE_KIND:
        return pyucs_to_num(PyUnicode_1BYTE_DATA(s), len(s))
    elif kind == PyUnicode_2BYTE_KIND:
        return pyucs_to_num(PyUnicode_2BYTE_DATA(s), len(s))
    elif kind == PyUnicode_4BYTE_KIND:
        return pyucs_to_num(PyUnicode_4BYTE_DATA(s), len(s))
    else:
        raise AssertionError("Unsupported unicode kind")

cpdef array array_extend_buffer_from_memoryview(array self, const u8[:] view):
    array_extend_buffer(self, &view[0], view.nbytes)
    return self

cdef inline void array_extend_buffer(array self, void* ptr, u64 size):
    cdef u64 l=Py_SIZE(self)
    resize_smart(self, l + size)
    memcpy(self.data.as_chars+l, ptr, size)

cdef u8* py_malloc(u64 size):
    cdef u8* ptr = <u8*>PyMem_Malloc(size)
    if ptr != NULL:
        return ptr
    else:
        raise_mem_err(size)

cdef u8* py_calloc(u64 size):
    cdef u8* ptr = <u8*>PyMem_Calloc(size,1)
    if ptr != NULL:
        return ptr
    else:
        raise_mem_err(size)

cdef raise_mem_err(size):
    e = MemoryError(f'alloc {size}bytes fault ')
    e.size = size
    raise e

#-----------------------------------------------------------------------------------------------------------------------
ctypedef object pyfunc()

cdef new_1_list(): return []
cdef new_1_set(): return set()
cdef new_5_list(): return ([],[],[],[],[])
cdef new_3_list(): return ([],[],[])
cdef new_2_list(): return ([],[])
cdef new_1_dict(): return {}
cdef new_U64(): return  U64().set(0)

cdef default_dict_get(dict d, key, pyfunc* default):
    try:
        return d[key]
    except KeyError:
        r = default()
        d[key] = r
        return r

B, Q = 'B', 'Q'

cpdef array new_array(u64 size):
    cdef array arr = array(B)
    resize(arr, size)
    return arr

ctypedef fused listuple:
    list
    tuple

cpdef u64 bisect_obj_in(listuple items, item):
    cdef:
        uint low=0, high=len(items), mi, last=high-1
        object cmp_r, mid
        #
    while (low < high):
        mi = (low + high) >> 1
        mid = items[mi]
        if mid < item:
            low = mi + 1
        elif mid > item:
            high = mi
        else:
            return mi
    return last

cpdef u64 bisect_obj_in_by_cmp_func(listuple items, item, cmp):
    cdef:
        uint mi, low=0, high=len(items)
        object cmp_r
    while (low < high):
        mi = (low + high) >> 1
        mid = items[mi]
        cmp_r = cmp(mid, item)
        if cmp_r is True:
            low = mi + 1
        elif cmp_r is False:
            high = mi
        else:
            return mi
    return UINT64_MAX

cpdef u64 bisect_str_in(listuple items, str item):
    cdef:
        uint low=0, high=len(items), mi, last = high - 1
        object cmp_r, mid
        #
    while (low < high):
        mi = (low + high) >> 1
        mid = items[mi]
        if mid < item:
            low = mi + 1
        elif mid > item:
            high = mi
        else:
            return mi
    return last

cpdef int _cmp_str(str a,str b):
    cdef int r
    if len(a) < len(b):
        return -1
    elif len(a) > len(b):
        return 1
    else:
        r=PyUnicode_Compare(a, b)
        return r
        '''if r < 0: return True
        elif r > 0: return False
        else: return None'''

#-----------------------------------------------------------------------------------------------------------------------
cdef class Obj2:
    cdef readonly object obj0,obj1
    def __init__(self, obj0, obj1):
        self.obj0, self.obj1 = obj0, obj1
cdef u64 try_get_u64(object obj):
    cdef U64 v
    if isinstance(obj, U64):
        return obj.val
    elif isinstance(obj, int):
        return obj
    else:
        raise TypeError

cdef class U64:
    cdef readonly u64 val
    cpdef U64 set(self, u64 val):
        self.val = val
        return self
    def __repr__(self):
        return f'U64({self.val})'
    def __str__(self):
        return f'{self.val}'
    def __hash__(self):
        return self.val
    def __eq__(self, other):
        cdef u64 o
        if isinstance(other, U64):
            o=other
            return self.val == other.val
        elif isinstance(other, int):
            return self.val == other
        else:
            raise TypeError("U64 can only be compared with U64 or int")


cdef u64 POW2=20,MAX_CACHE_U64 = 1<<20, MAX_CACHE_U64s1=1<<21
cdef tuple cache_u64s=PyTuple_New(MAX_CACHE_U64), cache_u64s1=PyTuple_New(MAX_CACHE_U64s1)

init_cache_u64s()
#for num in cache_u64s: print(num, type(num))
cdef init_cache_u64s():
    cdef u64 i
    for i in range(MAX_CACHE_U64):
        o=U64().set(i)
        Py_INCREF(o)
        PyTuple_SET_ITEM(cache_u64s, i, o)
        #print(o, type(o), cache_u64s[i], type(cache_u64s[i]))
    for i in range(MAX_CACHE_U64s1):
        PyTuple_SET_ITEM(cache_u64s1, i, None)

cpdef U64 get_U64(u64 i):
    cdef uint ii
    #cdef U64 v, vv
    #print(f'get_U64 debug {i}')
    if i < MAX_CACHE_U64:
        v=<object>PyTuple_GET_ITEM(cache_u64s, i)
        #print(v, type(v))
        return v
    else:
        return U64().set(i)

cdef class Buffer:
    cdef :
        u8* ptr
        readonly u64 size
    cdef Buffer set(self, u8* ptr, u64 size):
        self.ptr, self.size = ptr, size
        return self


cdef class BufferStealer(Buffer):
    def __dealloc__(self):
        free(self.ptr)

cpdef counter_add_1(dict self, key):
    cdef U64 count
    try:
        count = self[key]
        self[key]=get_U64(count.val+1)
    except KeyError:
        count = get_U64(1)
        self[key] = count

cpdef counter_sub_1(dict self, key):
    cdef U64 count
    count = self[key]
    count.val -= 1

cpdef dict_append(dict self, key, item):
    cdef list l=default_dict_get(self, key, &new_1_list)
    l.append(item)



cpdef uint num_storage_size(u64 size):
    if size<UINT8_MAX:
        return 1
    elif size<UINT16_MAX:
        return 2
    elif size<UINT32_MAX:
        return 4
    else:
        return 8

cpdef get_all_none_tuple(u64 l):
    cdef uint i
    tp = PyTuple_New(l)
    for i in range(l):
        PyTuple_SET_ITEM(tp, i, None)

cpdef counter_update(dict all_counter, dict old_counter, dict new_counter):
    cdef U64 v0, v1, v2
    for key, v2 in new_counter.items():
        try:
            v0=all_counter[key]
        except KeyError:
            all_counter[key]=v0
        else:
            try:
                v1 = old_counter[key]
            except KeyError:
                all_counter[key] = get_U64(v0.val-v2.val)
            else:
                if v2.val > v1.val:
                    all_counter[key] = get_U64(v0.val+v2.val-v1.val)
                else:
                    all_counter[key]=get_U64(v0.val - v2.val + v1.val)
#-----------------------------------------------------------------------------------------------------------------------

cpdef tuple_set_item(tuple tp, u64 i, val):
    o=<object>PyTuple_GET_ITEM(tp, i)
    if o is not None:
        Py_DECREF(o)
    Py_INCREF(val)
    PyTuple_SET_ITEM(tp, i, val)
    return o

cpdef get_ref_count(o):
    return (<PyObject* >o).ob_refcnt

cpdef set_ref_count(o, u64 v):
    (<PyObject* >o).ob_refcnt=v

def test_tuple_set_item(tuple tp, u64 i, val):
    if i<len(tp):
        refcnt_val = get_ref_count(val)
        o = tuple_set_item(tp, i, val)
        refcnt_o = get_ref_count(o)
        return refcnt_o, refcnt_val
    else:
        raise IndexError
#-----------------------------------------------------------------------------------------------------------------------
class MyRuntimeError(RuntimeError):
    pass
